
struct ListNode
{
   int val;
   ListNode *next;
   ListNode():val(0),next(nullptr){}
   ListNode(int x):val(x),next(nullptr){}
   ListNode(int x,ListNode *next):val(x),next(next){}
};
//方法1
//链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。
//这道题要求删除链表中所有节点值等于特定值的节点，可以用递归实现。

//对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，
//然后判断head 的节点值是否等于给定的val。
//如果head 的节点值等于val，则head 需要被删除，
//因此删除操作后的头节点为head.next；
//如果head 的节点值不等于val，则head 保留，
//因此删除操作后的头节点还是head。

//递归的终止条件是head 为空，此时直接返回head。
//当head不为空时，递归地进行删除操作，
//然后判断head 的节点值是否等于val并决定是否要删除head。

class Solution
{
public:
ListNode *removeElements(ListNode *head,int val)
{
   //递归终止条件
   if (head==nullptr)
   {
      return head;
   }
   //
   head->next=removeElements(head->next,val);
   if (head->val=val)
   {
      return head->next;
   }
   else
      return head;
}
};

//方法2 迭代
//也可以用迭代的方法删除链表中所有节点值等于特定值的节点。
//用temp 表示当前节点。如果temp 的下一个节点不为空且下一个节点的节点值等于给定的val，
//则需要删除下一个节点。删除下一个节点可以通过以下做法实现：

//temp.next=temp.next.next

//如果temp 的下一个节点的节点值不等于给定的val，则保留下一个节点,
//将temp 移动到下一个节点即可。

//当temp 的下一个节点为空时，链表遍历结束，
//此时所有节点值等于val 的节点都被删除

//具体实现方面，由于链表的头节点head 有可能需要被删除，
//因此创建哑节点dummyHead，令 dummyHead.next=head
//初始化 temp=dummyHead，然后遍历链表进行删除操作。
//最终返回dummyHead.next 即为删除操作后的头节点。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        struct ListNode* dummyHead = new ListNode(0, head);
        //创建哑节点
        //哑节点是在处理与链表相关的操作时，设置在链表头之前的指向链表头的节点，用于简化与链表头相关的操作。
        struct ListNode* temp = dummyHead;
        while (temp->next != nullptr) {
            if (temp->next->val == val) {
               //删除单链表中的节点
                temp->next = temp->next->next;
            } else {
               //节点后移一位
                temp = temp->next;
            }
        }
        return dummyHead->next;
    }
};

